package com.arron.algorithm.leetcodetop100.二分查找;

/**
 *
 */
public class 搜索旋转排序数组II {

    //如果包 搜索数组 含重复元素
    public boolean search2(int[] nums, int target) {
        if (nums.length == 1){
            return nums[0] == target;
        }
        int left = 0,right = nums.length-1;

        while (left<= right){

            int mid = left+(right-left)/2;

            if (nums[left] == target) return true;
            if (nums[right] == target) return true;
            if (nums[mid] == target) return true;
            //去重
            if(nums[left]  == nums[mid] && nums[mid]== nums[right]){
                right--;
                left++;
                continue;
            }
            if (nums[left] <= nums[mid]){
                //则说明左区间是有序的
                if (nums[left]<target && target< nums[mid]){
                    left= left+1;
                    right = mid -1;
                }else {
                    left = mid+1;
                }

            }else {
                //右区间是有序，直接判断是否在右边区间
                if (nums[mid]<target && target< nums[right]){
                    left = mid+1;
                    right = right-1;
                }else {
                    right = mid-1;
                }

            }
        }

        return false;

    }
}
